`
https://leetcode.cn/problems/number-of-squareful-arrays/
`

/**
 * @param {number[]} nums
 * @return {number}
 */
var numSquarefulPerms = function (nums) {
  let res = 0
  const used = new Array(nums.length).fill(false)
  const track = []

  // 排序，把相同的数字挨在一起，方便剪枝
  nums.sort((a, b) => a - b)

  function backtrack() {
    // 找到一个结果
    if (track.length === nums.length) {
      res++
      return
    }

    for (let i = 0; i < nums.length; i++) {
      // 用过了
      if (used[i]) continue

      // 剪枝，避免生成重复的排列
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue

      // 排除掉不符合题目要求的
      if (track.length !== 0 && !isSquareful(track[track.length - 1], nums[i])) {
        continue
      }

      used[i] = true
      track.push(nums[i])
      backtrack()
      track.pop()
      used[i] = false
    }
  }

  backtrack()
  return res
};

function isSquareful(a, b) {
  const num = Math.sqrt(a + b)
  return Math.floor(num) === num
}